package lastmpd;

/*
 * Copyright (C) 2010 Mark Breddemann
 * 
 * This program is free software; you can redistribute it and/or modify it under the
 * terms of the GNU General Public License as published by the Free Software Foundation;
 * either version 3 of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with this
 * program; if not, see <http://www.gnu.org/licenses/>.
 */

public class LevenshteinDistance {
//	}
	
   public static int levenshtein(String original, String input) {
	int[][] matrix;
   	/* Schritt 1 */
   	int n = original.length();
	   int m = input.length();
	   int cost,minimum;
	   char chOriginal,chInput;
	   
	   if(n == 0 || m == 0)
	   	return 0;
		
		int hoehe = n + 1;
		int breite = m + 1;
		
		matrix = new int[hoehe][breite];
		
		/* Schritt 2 */
		for(int i = 0;i < hoehe;i++)
			matrix[i][0] = i;
	
		for(int j = 0;j < breite;j++)
			matrix[0][j] = j;
			
		/* Schritte 3 - 6 */
		for(int i = 1;i < hoehe;i++) {
			chOriginal = original.charAt(i-1);
			
			for(int j = 1;j < breite;j++) {
				chInput = input.charAt(j-1);
				
				/* Wenn Zeichen übereinstimmen -> Keine Substitution etc. notwendig -> 0 Kosten */
				if(chOriginal == chInput)
					cost = 0;
				else
					cost = 1;
				
				/* Berechnung des Minimums */	
				minimum = matrix[i-1][j]+1;
				
				if((matrix[i][j-1]+1) < minimum)
					minimum = matrix[i][j-1]+1;
				
				if((matrix[i-1][j-1] + cost) < minimum)
					minimum = matrix[i-1][j-1] + cost;

				matrix[i][j] = minimum;
			}
		}
		
		return matrix[n][m];	
   }
   
}